On Guarding Nested Fixpoints
Identifieur interne : 000237 ( LNCS/Analysis ); précédent : 000236; suivant : 000238On Guarding Nested Fixpoints
Auteurs : Helmut Seidl [Allemagne] ; Andreas Neumann [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1999.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Abstract: For every hierarchicalsystem of equations S over some complete and distributive lattice we construct an equivalent system with the same set of variables which additionally is guarded. The price to be paid is that the resulting right-hand sides may grow exponentially. We therefore present methods how the exponentialbl ow-up can be avoided. Especially, the loop structure of the variable dependence graph is taken into account. Also we prove that size O(m· S) suffices whenever S originates from a fixpoint expression where the nesting-depth of fixpoints is at most m. Finally, we sketch an application to regular tree pattern-matching.
Url:
DOI: 10.1007/3-540-48168-0_34
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001201
- to stream Istex, to step Curation: 001089
- to stream Istex, to step Checkpoint: 000D69
- to stream Main, to step Merge: 002473
- to stream PascalFrancis, to step Corpus: 000F86
- to stream PascalFrancis, to step Curation: 001808
- to stream PascalFrancis, to step Checkpoint: 000D74
- to stream Main, to step Merge: 002526
- to stream Main, to step Curation: 002119
- to stream Main, to step Exploration: 002119
- to stream LNCS, to step Extraction: 000237
Links to Exploration step
ISTEX:1D210FA7B96EBF8DF77AC10C91B43B82BD30AFD2Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On Guarding Nested Fixpoints</title><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name></author><author><name sortKey="Neumann, Andreas" sort="Neumann, Andreas" uniqKey="Neumann A" first="Andreas" last="Neumann">Andreas Neumann</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:1D210FA7B96EBF8DF77AC10C91B43B82BD30AFD2</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1007/3-540-48168-0_34</idno><idno type="url">https://api.istex.fr/document/1D210FA7B96EBF8DF77AC10C91B43B82BD30AFD2/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001201</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001201</idno><idno type="wicri:Area/Istex/Curation">001089</idno><idno type="wicri:Area/Istex/Checkpoint">000D69</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000D69</idno><idno type="wicri:doubleKey">0302-9743:1999:Seidl H:on:guarding:nested</idno><idno type="wicri:Area/Main/Merge">002473</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:99-0547829</idno><idno type="wicri:Area/PascalFrancis/Corpus">000F86</idno><idno type="wicri:Area/PascalFrancis/Curation">001808</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000D74</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000D74</idno><idno type="wicri:doubleKey">0302-9743:1999:Seidl H:on:guarding:nested</idno><idno type="wicri:Area/Main/Merge">002526</idno><idno type="wicri:Area/Main/Curation">002119</idno><idno type="wicri:Area/Main/Exploration">002119</idno><idno type="wicri:Area/LNCS/Extraction">000237</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On Guarding Nested Fixpoints</title><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV - Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Neumann, Andreas" sort="Neumann, Andreas" uniqKey="Neumann A" first="Andreas" last="Neumann">Andreas Neumann</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV - Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1999</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">1D210FA7B96EBF8DF77AC10C91B43B82BD30AFD2</idno><idno type="DOI">10.1007/3-540-48168-0_34</idno><idno type="ChapterID">34</idno><idno type="ChapterID">Chap34</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computer theory</term><term>Logical programming</term><term>Program complexity</term><term>Program proof</term><term>Program transformation</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Complexité programme</term><term>Informatique théorique</term><term>Preuve programme</term><term>Programmation logique</term><term>Transformation programme</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: For every hierarchicalsystem of equations S over some complete and distributive lattice we construct an equivalent system with the same set of variables which additionally is guarded. The price to be paid is that the resulting right-hand sides may grow exponentially. We therefore present methods how the exponentialbl ow-up can be avoided. Especially, the loop structure of the variable dependence graph is taken into account. Also we prove that size O(m· S) suffices whenever S originates from a fixpoint expression where the nesting-depth of fixpoints is at most m. Finally, we sketch an application to regular tree pattern-matching.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country></list><tree><country name="Allemagne"><noRegion><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name></noRegion><name sortKey="Neumann, Andreas" sort="Neumann, Andreas" uniqKey="Neumann A" first="Andreas" last="Neumann">Andreas Neumann</name><name sortKey="Neumann, Andreas" sort="Neumann, Andreas" uniqKey="Neumann A" first="Andreas" last="Neumann">Andreas Neumann</name><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000237 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000237 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= LNCS
|étape= Analysis
|type= RBID
|clé= ISTEX:1D210FA7B96EBF8DF77AC10C91B43B82BD30AFD2
|texte= On Guarding Nested Fixpoints
}}
| This area was generated with Dilib version V0.6.31. |  |